Jupyter at Bryn Mawr College
Public notebooks: /services/public/dblank / CS206 Data Structures / 2016-Spring / Notebooks

1. Self-Balancing Search Trees

We looked at Search Trees previously, and we knew that they were better if balanced. Now we explore how to automatically keep them balanced.

1.1 Tree Balance and Rotation

Most of the algorithms that we will discuss use the ideas of balance and rotation.

1.2 AVL Trees

We have explored AVL trees very thoroughly.

1.3 Red-Black Trees

Rules (Invariants):

Adding a new node:

• initial color is red
• if parent is black, you are done
• else if parent is red, and parent has a red sibling
  • change grandparent to red
  • change parent/sibling to black
  • if root is red, change to black
• else parent is read, but no red sibling
  • grandparent to red
  • parent black
  • rotate around grandparent

Fig 9.22:

1. insert 35
2. 30 and 10 are red, so:
3. change 10, 30, 20
4. done

Fig 9.23:

1. insert 35
2. change 20 and 30
3. rotate grandparent left
4. done

Fig 9.25:

1. insert 25
2. rotate parent to right
3. rotate grandparent to left

Red-Black Simulation:

https://www.cs.usfca.edu/~galles/visualization/RedBlack.html

Other notes:

• TreeMap - Map interface implemented by a Red-Black Tree, implements SortedSet
  • get, put, remove, containsKey - all O(log n)

1.4 Non-Binary Trees

1.4.1 Two-Three (2-3) Tree

Children are either 2-node or 3-node

1.4.2 B-Tree

• n children per node
• useful as a database with fixed "block" size (disk)
• each node has between n/2 and n children

If n = 200, then each node has between 100 and 200 children. Tree of height 4 could hold:

$$ 100 ^ 4 $$

or 100 million values.

1.4.3 B+ Tree

1.4.4 One-Two-Three-Four (1-2-3-4) Tree

A B-Tree with n set to 4.

1.4.4.1 Comparision of 2-3-4 Trees with Red-Black